广义线性可分支持向量机¶
当训练集 $T$ 的两类样本线性可分时, 除了普通支持向量分布在两个分类 边界 $\omega^{T} \boldsymbol{x}+\boldsymbol{b}=\pm \mathbf{1}$ 上外, 其余的所有样本点都分布在分类边界以外。此时构 造的超平面是硬间隔超平面。当训练集 $T$ 的两类样本近似线性可分时, 即允 许存在不满足约束条件 $$ c_{i}\left(\omega^{T} a_{i}+b\right) \geq 1 $$ 的样本点后，仍然能继续使用超平面进行划分。只是这时要对间隔进行“软 化", 构造软间隔超平面。简言之就是在两个分类边界 $\omega^{T} \boldsymbol{x}+\boldsymbol{b}=\pm \mathbf{1}$ 之间允许 出现样本点, 这类样本点被称为边界支持向量。显然两类样本点集的凸包是 相交的, 只是相交的部分较小。广义线性支持向量分类机如图所示。
软化的方法是通过引入松弛变量 $$ \xi_{i} \geq 0, \quad i=1,2, \cdots, N, $$ 来得到“软化”的约束条件 $$ c_{i}\left(\omega^{T} a_{i}+b\right) \geq 1-\xi_{i} \quad i=1,2, \cdots, N . $$ 当 $\xi_{i}$ 充分大时, 样本点总是满足上述的约束条件, 但是也要设法避免 $\xi_{i}$ 取太 大的值, 为此要在目标函数中对它进行惩罚, 得到如下的二次规划问题 $$ \text { s.t. }\left\{\begin{array}{l} \min \frac{1}{2}\|\omega\|^{2}+C \sum_{i=1}^{N} \xi_{i}, \\ \xi_{i} \geq 0, \quad i=1,2, \cdots, N . \end{array}\right. $$ 其中 $C>0$ 是一个惩罚参数。
其 Lagrange 函数如下 $$ \boldsymbol{L}(\boldsymbol{\omega}, \boldsymbol{b}, \boldsymbol{\xi}, \boldsymbol{\alpha}, \gamma)=\frac{1}{2}\|\omega\|^{2}+C \sum_{i=1}^{N} \xi_{i}-\sum_{i=1}^{N} \alpha_{i}\left(\boldsymbol{c}_{i}\left(\boldsymbol{\omega}^{T} \boldsymbol{a}_{i}+\boldsymbol{b}\right)-\mathbf{1}+\xi_{i}\right)-\sum_{i=1}^{N} \gamma_{i} \xi_{i}, $$ 其中 $\gamma_{i} \geq \mathbf{0}, \xi_{i} \geq \mathbf{0}$ 。原问题的对偶问题如下 $$ \begin{aligned} &\max _{\alpha}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} c_{i} c_{j} \alpha_{i} \alpha_{j} a_{i}^{T} a_{j}+\sum_{i=1}^{N} \alpha_{i}, \\ &\text { s.t. }\left\{\begin{array}{l} \sum_{i=1}^{N} c_{i} \alpha_{i}=0, \\ 0 \leq \alpha_{i} \leq C, \quad i=1,2, \cdots, N . \end{array}\right. \end{aligned} $$
求解上述最优化问题, 得到最优解 $\alpha^{*}=\left[\alpha_{1}^{*}, \alpha_{2}^{*}, \cdots, \alpha_{N}^{*}\right]^{T}$, 计算 $$ \omega^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} c_{i} a_{i}, $$ 选择 $\alpha^{*}$ 的一个正分量 $0<\alpha_{j}^{*}<C$, 并以此计算 $$ b^{*}=c_{j}-\sum_{i=1}^{N} c_{i} \alpha_{i}^{*} a_{i}^{T} a_{j} . $$ 于是构造分类超平面 $\omega^{* T} \boldsymbol{x}+\boldsymbol{b}^{*}=\mathbf{0}$, 并由此求得分类函数 $$ f(x)=\operatorname{sgn}\left(\sum_{i=1}^{N} \alpha_{i}^{*} c_{i} a_{i}^{T} x+b^{*}\right) . $$ 从而对末知样本进行分类, 可见当 $C=\infty$ 时, 就等价于线性可分的情形。
参考文献
- 司守奎，孙玺菁 Python数学实验与建模